This application is based on an application No. H11-162113 filed in Japan, the content of which is hereby incorporated by reference.
1. Field of the Invention
The present invention relates to a variable length code decoding device, digital broadcast receiving apparatus, and DVD reproducing apparatus for decoding a compressed code stream into original signals.
2. Description of the Prior Art
Technology for efficiently compressing and encoding images, represented by MPEG (Moving Picture Experts Group), has been increasingly explored in recent years.
FIG. 27 is a block diagram showing a conventional variable length code decoding device for decoding variable length codewords. In the figure, a bit stream buffer 1001 acquires a bit stream of an encoded moving image from an outside source and retains it. A bit string extracting unit 1002 extracts a bit string as long as the maximum variable length from the beginning of the bit stream in the bit stream buffer 1001, and outputs the extracted bit string to a bit length judging unit 1003. The bit length judging unit 1003 detects a codeword from the received bit string and calculates the bit length of the detected codeword. The bit length judging unit 1003 outputs the calculated bit length to a variable length code decoding unit 1004 and the bit string extracting unit 1002, and outputs the codeword to the variable length code decoding unit 1004. The bit string extracting unit 1002 shifts the bit string extract position by the received bit length. The variable length code decoding unit 1004 decodes the codeword in accordance with a variable length code table held therein, and so generates a run (the number of consecutive zero coefficients) and a level (the value of the immediately following non-zero coefficient). The variable length code decoding unit 1004 outputs the generated run and level respectively to an output controlling unit 1005 and an output selecting unit 1007. The output controlling unit 1005 controls the output selecting unit 1007. If the run is not 0, the output selecting unit 1007 selects the constant 0 outputted from a constant generating unit 1006 a number of times equivalent to the run, and then selects the level received from the variable length code decoding unit 1004. If the run is 0, the output selecting unit 1007 selects the level. A buffer 1008 stores values selected by the output selecting unit 1007. An inverse quantizing unit 1009 reads the values from the buffer 1008 and inverse quantizes them. As a result, a block of DCT (Discrete Cosine Transform) pixel values in a spatial frequency region is generated. Note that detecting one codeword from a bit string by the bit length judging unit 1003 is done according to a well known method described in xe2x80x9cISO/IEC 13818-2xe2x80x9d ISO/IEC JTC1, published by ISO/IEC (May 31, 1995), so that its explanation has been omitted.
However, this variable length code decoding device has the following problem. Since variable length codewords are extracted and decoded one at a time, it takes long time to decode all of the codewords, which causes decreases in processing speed of the overall system. Although such decreases in processing speed could be avoided by increasing the system""s operating frequency, this will incur increases in cost and power consumption of the system.
To overcome the above problem, the present invention aims to provide a variable length code decoding device, digital broadcast receiving apparatus, and DVD reproducing apparatus that can decode a greater number of variable length codewords within a fixed time period.
The above object can be fulfilled by a variable length code decoding device including: a code extracting unit for extracting two consecutive codewords from a compressed code stream that is made up of a sequence of variable length codewords; and a parallel decoding unit for decoding the extracted two codewords in parallel.
With the above construction, the variable length code decoding device extracts two codewords from a compressed code stream and decodes them in parallel, with it being possible to increase the number of variable length codewords which can be decoded in a fixed time period.
Here, the compressed code stream may include a plurality of codewords that have each been generated as a result of quantizing and entropy coding at least one signal, hereafter referred to as a signal set, which belongs to a block of signals each generated by applying orthogonal transform to image data, wherein the code extracting unit extracts the two consecutive codewords out of the plurality of codewords included in the compressed code stream, and wherein the parallel decoding unit includes: a code decoding unit for entropy decoding the extracted two codewords in parallel to generate two decoded words; and a signal reconstructing unit for performing inverse quantization with the two decoded words in parallel to reconstruct two original signal sets.
With the above construction, the compressed code stream contains codewords obtained by coding signals generated from image data. The two codewords extracted from this compressed code stream are entropy decoded in parallel to reconstruct original signals. In so doing, a greater number of variable length codewords can be decoded within a fixed time period.
Here, each codeword may have been generated by entropy coding a run-level pair that represents a quantized signal set, the run-level pair being made up of a run which is a number of zero signals in the quantized signal set and a level which is a value of an immediately following nonzero signal in the quantized signal set, wherein the code extracting unit extracts the two consecutive codewords as first and second codewords, and includes: a position storing unit for storing position information which specifies a position of the first codeword in the compressed code stream; a first extracting unit for extracting from the compressed code stream the first codeword located in the position specified by the position information, and calculating a length of the first codeword; and a second extracting unit for extracting from the compressed code stream the second codeword located in a position specified by a sum of the position information and the calculated length, wherein the code decoding unit entropy decodes the extracted first and second codewords to generate first and second run-level pairs as the two decoded words, and includes: a first decoding unit for entropy decoding the first codeword into the first run-level pair; and a second decoding unit for entropy decoding the second codeword into the second run-level pair, and wherein the signal reconstructing unit reconstructs the two original signal sets based on the first and second run-level pairs.
With the above construction, the two codewords are extracted from the compressed code stream in sequence and are entropy decoded in parallel into two run-level pairs.
Here, the first decoding unit may include: a first table having areas which each have an address no greater than a first predetermined length and store a run-level pair, the address being a codeword generated when entropy coding the run-level pair; a second table having areas which each have an address greater than the first predetermined length and store a unique value; a third table having a separate area for each of the areas in the second table, the area in the third table having an address equal to a value stored in the area in the second table and storing a run-level pair, where an address of the area in the second table is a codeword generated when entropy coding the run-level pair stored in the area in the third table; and a first decode controlling unit for when the first codeword is no greater than the first predetermined length, retrieving from the first table a run-level pair stored in an area whose address is the first codeword, and setting the retrieved run-level pair as the first run-level pair, and when the first codeword is greater than the first predetermined length, reading from the second table a value stored in an area whose address is the first codeword, retrieving from the third table a run-level pair stored in an area whose address is the read value, and setting the retrieved run-level pair as the first run-level pair.
With the above construction, a variable length code table in the first decoding unit has a bi-level structure made up of a fixed table (the first table) and an associative memory (the second and third tables). The size of such a variable length code table is smaller than a variable length code table structured as a single table.
Here, the second decoding unit may include: a fourth table having areas which each have an address no greater than the first predetermined length and store a run-level pair, the address being a codeword generated when entropy coding the run-level pair; a fifth table having areas which each have an address greater than the first predetermined length and store a unique value; a sixth table having a separate area for each of the areas in the fifth table, the area in the sixth table having an address equal to a value stored in the area in the fifth table and storing a run-level pair, where an address of the area in the fifth table is a codeword generated when entropy coding the run-level pair stored in the area in the sixth table; and a second decode controlling unit for when the second codeword is no greater than the first predetermined length, retrieving from the fourth table a run-level pair stored in an area whose address is the second codeword, and setting the retrieved run-level pair as the second run-level pair, and when the second codeword is greater than the first predetermined length, reading from the fifth table a value stored in an area whose address is the second codeword, retrieving from the sixth table a run-level pair stored in an area whose address is the read value, and setting the retrieved run-level pair as the second run-level pair.
With the above construction, a variable length code table in the second decoding unit has a bi-level structure made up of a fixed table (the fourth table) and an associative memory (the fifth and sixth tables). The size of such a variable length code table is smaller than a variable length code table structured as a single table.
Here, the second extracting unit may extract a codeword generated by entropy coding a run-level pair whose run is 0, as the second codeword, wherein the second decoding unit includes: a seventh table having areas which each have an address and store a level of a run-level pair whose run is 0, the address being a codeword generated when entropy coding the run-level pair; and a second decode controlling unit for retrieving from the seventh table a level stored in an area whose address is the second codeword, and pairing the retrieved level with a run being 0 to generate the second run-level pair.
With the above construction, a variable length code table (the seventh table) which relates only to codewords corresponding to run-level pairs whose runs are 0 is provided in the second decoding unit. Accordingly, if any codeword and a codeword generated from a run-level pair whose run is 0 are adjacent in the compressed code stream, these two codewords can be decoded in parallel by means of the first and second decoding units. Also, the size of the variable length code table in the second decoding unit can be reduced.
Here, the second extracting unit may extract a codeword no greater than a second predetermined length as the second codeword, wherein the second decoding unit includes: an eighth table having areas which each have an address no greater than the second predetermined length and store a run-level pair, the address being a codeword generated when entropy coding the run-level pair; and a second decode controlling unit for retrieving from the eighth table a run-level pair stored in an area whose address is the second codeword, and setting the retrieved run-level pair as the second run-level pair.
With the above construction, a variable length code table (the eighth table) which relates only to short codewords (no greater than the second predetermined length) is provided in the second decoding unit. Accordingly, if any codeword and a short codeword are adjacent in the compressed code stream, these two codewords can be decoded in parallel by means of the first and second decoding units. Also, the size of the variable length code table in the second decoding unit can be reduced.
Here, the signal reconstructing unit may include: a first address calculating unit for calculating, based on the first run-level pair generated by the first decoding unit, a first address showing a location of a level of the first run-level pair within a block; a second address calculating unit for calculating, based on the second run-level pair generated by the second decoding unit, a second address showing a location of a level of the second run-level pair within the block; a first inverse quantizing unit for inverse quantizing the level of the first run-level pair using the calculated first address, to generate a first coefficient; a second inverse quantizing unit for inverse quantizing the level of the second run-level pair using the calculated second address, to generate a second coefficient; and a reconstructing unit for reconstructing the two original signal sets using a combination of the first address and the first coefficient and a combination of the second address and the second coefficient.
With the above construction, address calculation and inverse quantization for one run-level pair are carried out in parallel with address calculation and inverse quantization for the other run-level pair, which accelerates computations of the overall inverse quantization.
Here, the reconstructing unit may include: a coefficient storing unit for storing address-coefficient pairs; a coefficient writing unit for writing the combination of the first address and the first coefficient and the combination of the second address and the second coefficient into the coefficient storing unit as two address-coefficient pairs; a block storing unit having areas each of which has an address and initially stores a zero value; a block writing unit for sequentially reading the two address-coefficient pairs from the coefficient storing unit, and writing a coefficient of each of the read address-coefficient pairs into an area in the block storing unit specified by an address of the address-coefficient pair; and a signal generating unit for reading values from part of the areas in the block storing unit and generating the two original signal sets from the read values.
With the above construction, generated signals can be written into a buffer independently of the processing of an external unit which reads out the signals.
Here, the coefficient storing unit may have areas each of which is given a flag being initially OFF and is used for storing an address-coefficient pair, wherein the coefficient writing unit writes the two address-coefficient pairs into respective areas in the coefficient storing unit whose flags are OFF, and then turns the flags ON, and the block writing unit sequentially reads the address-coefficient pairs from the areas with the ON flags in the coefficient storing unit, and, having read the address-coefficient pairs, turns the flags OFF.
Here, the areas in the block storing unit may each be given a flag which is initially OFF, wherein the block writing unit, having written the coefficient into the area in the block storing unit specified by the address, turns a flag of the area ON, and the signal generating unit, having generated the two original signal sets, turns ON flags in the block storing unit OFF.
With the above construction, the need for writing 0 into every area to delete its storage content is negated.
Here, the variable length code decoding device may further include a selection accepting unit for accepting a selection between decoding of a first compressed code stream and decoding of first and second compressed code streams, the first compressed code stream being the compressed code stream and the second compressed code stream being another compressed code stream made up of a sequence of variable length codewords, the second compressed code stream including a plurality of codewords that have each been generated as a result of quantizing and entropy coding a signal set which belongs to a block of signals each generated by applying orthogonal transform to image data, wherein the code extracting unit (a) extracts the two consecutive codewords from the first compressed code stream in a first case where the decoding of the first compressed code stream is selected, and (b) extracts two codewords respectively from the first and second compressed code streams in a second case where the decoding of the first and second compressed code streams is selected, and wherein the code decoding unit entropy decodes the extracted two codewords in parallel.
With the above construction, the variable length code decoding device can selectively perform the decoding of a single compressed code stream and the decoding of two compressed code streams. In the decoding of the single compressed code stream, two codewords are extracted from the compressed code stream and entropy decoded in parallel to reconstruct original signals, so that a greater number of variable length codewords can be decoded within a fixed time period.
Here, the code extracting unit may extract, as first and second codewords, the two consecutive codewords from the first compressed code stream in the first case and the two codewords respectively from the first and second compressed code streams in the second case, and include: a position storing unit for storing first position information and second position information, the first position information specifying a position of the first codeword in the first compressed code stream, and the second position information specifying a position of the second codeword in the second compressed code stream; a first extracting unit for extracting from the first compressed code stream the first codeword located in the position specified by the first position information, and calculating a length of the first codeword; and a second extracting unit for (a) in the first case extracting from the first compressed code stream the second codeword located in a position specified by a sum of the first position information and the calculated length, and (b) in the second case extracting from the second compressed code stream the second codeword located in the position specified by the second position information, and wherein the code decoding unit entropy decodes the extracted first and second codewords to generate two decoded words.
With the above construction, in the decoding of the single compressed code stream the two codewords are extracted in sequence, whereas in the decoding of the two compressed code streams two codewords are extracted respectively from the two compressed code streams.
Here, each codeword may have been generated by entropy coding a run-level pair that represents a quantized signal set, the run-level pair being made up of a run which is a number of zero signals in the quantized signal set and a level which is a value of an immediately following nonzero signal in the quantized signal set, wherein the code decoding unit entropy decodes the first and second codewords to generate first and second run-level pairs as the two decoded words, and includes: a first decoding unit for entropy decoding the first codeword into the first run-level pair; and a second decoding unit for entropy decoding the second codeword into the second run-level pair, and wherein the signal reconstructing unit reconstructs two original signal sets based on the first and second run-level pairs.
With the above construction, in the decoding of the single compressed code stream, the extracted two codewords are entropy decoded in parallel into two run-level pairs, and original signals are reconstructed from the generated run-level pairs. Accordingly, the number of variable length codewords which can be decoded in a fixed time period is increased. In the decoding of the two compressed code streams, on the other hand, the extracted two codewords are entropy decoded separately into two run-level pairs, and original signals are reconstructed from the generated run-level pairs.
Here, the signal reconstructing unit may include: a first address calculating unit for calculating, based on the first run-level pair generated by the first decoding unit, a first address showing a location of a level of the first run-level pair within a block; a second address calculating unit for calculating, based on the second run-level pair generated by the second decoding unit, a second address showing a location of a level of the second run-level pair within a block; a first inverse quantizing unit for inverse quantizing the level of the first run-level pair using the calculated first address, to generate a first coefficient; a second inverse quantizing unit for inverse quantizing the level of the second run-level pair using the calculated second address, to generate a second coefficient; and a reconstructing unit for reconstructing the two original signal sets using a combination of the first address and the first coefficient and a combination of the second address and the second coefficient.
With the above construction, in the decoding of the single compressed code stream, address calculation and inverse quantization for one run-level pair are carried out in parallel with address calculation and inverse quantization for the other run-level pair, which increases computations for the overall inverse quantization. In the decoding of the two compressed code streams, on the other hand, address calculation and inverse quantization for one run-level pair are carried out independently of address calculation and inverse quantization for the other run-level pair.
Here, the reconstructing unit may include: a first coefficient storing unit for storing address-coefficient pairs; a second coefficient storing unit for storing address-coefficient pairs; a coefficient writing unit for (a) in the first case writing the combination of the first address and the first coefficient and the combination of the second address and the second coefficient into the first coefficient storing unit as two address-coefficient pairs, and (b) in the second case writing the combination of the first address and the first coefficient into the first coefficient storing unit as an address-coefficient pair, and writing the combination of the second address and the second coefficient into the second coefficient storing unit as an address-coefficient pair; a first block storing unit having areas each of which has an address and initially stores a zero value; a second block storing unit having areas each of which has an address and initially stores a zero value; a block writing unit for (a) in the first case sequentially reading the two address-coefficient pairs from the first coefficient storing unit and writing a coefficient of each of the read address-coefficient pairs into an area in the first block storing unit specified by an address of the address-coefficient pair, and (b) in the second case reading the address-coefficient pair from the first coefficient storing unit and writing a coefficient of the read address-coefficient pair into an area in the first block storing unit specified by an address of the address-coefficient pair, and reading the address-coefficient pair from the second coefficient storing unit and writing a coefficient of the read address-coefficient pair into an area in the second block storing unit specified by an address of the address-coefficient pair; and a signal generating unit for (a) in the first case reading values from part of the areas in the first block storing unit and generating the two original signal sets from the read values, and (b) in the second case reading values from part of the areas in the first block storing unit and from part of the areas in the second block storing unit, and generating the two original signal sets from the read values.
With the above construction, in both the decoding of the single compressed code stream and the decoding of the two compressed code streams, generated signals can be written into at least one buffer independently of the processing of an external unit which reads out the signals.
Here, the compressed code stream may include a plurality of codewords that have each been generated as a result of quantizing and entropy coding at least one signal, hereafter referred to as a signal set, which belongs to a block of signals each generated by applying orthogonal transform to image data, wherein the code extracting unit extracts the two consecutive codewords out of the plurality of codewords included in the compressed code stream, the two consecutive codewords each being no greater than a third predetermined length, and wherein the parallel decoding unit includes: a code decoding unit for entropy decoding the extracted two codewords in parallel with reference to a code table, to generate two decoded words; and a signal reconstructing unit for performing inverse quantization with the two decoded codes in parallel to reconstruct two original signal sets.
With the above construction, when two short codewords (no greater than the third predetermined length) are adjacent in a compressed code stream that contains variable length codewords obtained by coding signals generated from image data, these two codewords are extracted from the compressed code stream and entropy decoded in parallel to reconstruct original signals. Accordingly, more variable length codewords can be decoded within a fixed time period.
Here, each codeword may have been generated by entropy coding a run-level pair that represents a quantized signal set, the run-level pair being made up of a run which is a number of zero signals in the quantized signal set and a level which is a value of an immediately following nonzero signal in the quantized signal set, wherein the code extracting unit extracts the two consecutive codewords as first and second codewords, and includes: a position storing unit for storing position information which specifies a position of the first codeword in the compressed code stream; and an extracting unit for extracting from the compressed code stream the first codeword located in the position specified by the position information, calculating a length of the first codeword, and extracting from the compressed code stream the second codeword located in a position specified by a sum of the position information and the calculated length, wherein the code decoding unit entropy decodes the extracted first and second codewords to generate first and second run-level pairs as the two decoded words, and includes: a ninth table having areas which each have an address obtained by concatenating two codewords each being no greater than the third predetermined length and store two run-level pairs, the former codeword being generated when entropy coding the former run-level pair, and the latter codeword being generated when entropy coding the latter run-level pair; and a decode controlling unit for retrieving from the ninth table two run-level pairs stored in an area whose address is a result of concatenating the first and second codewords in the stated order, and setting the retrieved former and latter run-level pairs respectively as the first and second run-level pairs, and wherein the signal reconstructing unit reconstructs the two original signal sets based on the first and second run-level pairs.
With the above construction, the two short codewords extracted from the compressed code stream are entropy decoded in parallel into two run-level pairs with reference to a code table (the ninth table), and the original signals are reconstructed from the generated run-level pairs.
Here, the signal reconstructing unit may include: a first address calculating unit for calculating, based on the first run-level pair generated by the code decoding unit, a first address showing a location of a level of the first run-level pair within a block; a second address calculating unit for calculating, based on the second run-level pair generated by the code decoding unit, a second address showing a location of a level of the second run-level pair within the block; a first inverse quantizing unit for inverse quantizing the level of the first run-level pair using the calculated first address, to generate a first coefficient; a second inverse quantizing unit for inverse quantizing the level of the second run-level pair using the calculated second address, to generate a second coefficient; and a reconstructing unit for reconstructing the two original signal sets using a combination of the first address and the first coefficient and a combination of the second address and the second coefficient.
With the above construction, address calculation and inverse quantization for one run-level pair are carried out in parallel with address calculation and inverse quantization for the other run-level pair, which accelerates computations for the overall inverse quantization.
Here, the reconstructing unit may include: a coefficient storing unit for storing address-coefficient pairs; a coefficient writing unit for writing the combination of the first address and the first coefficient and the combination of the second address and the second coefficient into the coefficient storing unit as two address-coefficient pairs; a block storing unit having areas each of which has an address and initially stores a zero value; a block writing unit for sequentially reading the two address-coefficient pairs from the coefficient storing unit and writing a coefficient of each of the read address-coefficient pairs into an area in the block storing unit specified by an address of the address-coefficient pair; and a signal generating unit for reading values from part of the areas in the block storing unit and generating the two original signal sets from the read values.
With the above construction, generated signals can be written into a buffer independently of the processing of an external unit IEIS. which reads out the signals.
Here, the compressed code stream may include coded control information elements that have been respectively generated as a result of entropy coding control information elements of at least two different types, the control information elements being used to control decoding of image data, wherein the code extracting unit extracts two consecutive coded control information elements from the compressed code stream as the two consecutive codewords, and wherein the parallel decoding unit includes a code decoding unit for entropy decoding the extracted two coded control information elements in parallel to generate two original control information elements.
With the above construction, a compressed code stream includes coded control information elements obtained by respectively coding control information elements of at least two different types. Two coded control information elements are extracted from this compressed code stream and are entropy decoded in parallel to reconstruct original control information elements, with it being possible to increase the number of variable length codewords which can be decoded in a fixed time period.
Here, the code extracting unit may extract the two consecutive coded control information elements as first and second codewords, and include: a position storing unit for storing position information which specifies a position of the first codeword in the compressed code stream; a first extracting unit for extracting from the compressed code stream the first codeword located in the position specified by the position information, and calculating a length of the first codeword; and a second extracting unit for extracting from the compressed code stream the second codeword located in a position specified by a sum of the position information and the calculated length, wherein the code decoding unit entropy decodes the first and second codewords to generate first and second control information elements as the two original control information elements, and includes: a first decoding unit for entropy decoding the first codeword into the first control information element; and a second decoding unit for entropy decoding the second codeword into the second control information element.
With the above construction, the two coded control information elements are extracted in sequence from the compressed code stream and entropy decoded in parallel into the original control information elements.
Here, the first decoding unit may include: a first control information table that has an address and stores codewords and control information elements corresponding to the codewords; a first address table that has a first address area storing the address of the first control information table; a first pointer holding unit for holding a first pointer which specifies the first address area in the first address table; and a first decode controlling unit for retrieving the address from the first address area in the first address table specified by the first pointer, detecting a control information element corresponding to the first codeword from the first control information table shown by the retrieved address, and setting the detected control information element as the first control information element.
Here, the second decoding unit may include: a second control information table that has an address and stores codewords and control information elements corresponding to the codewords; a second address table that has a second address area storing the address of the second control information table; a second pointer holding unit for holding a second pointer which specifies the second address area in the second address table; and a second decode controlling unit for retrieving the address from the second address area in the second address table specified by the second pointer, detecting a control information element corresponding to the second codeword from the second control information table shown by the retrieved address, and setting the detected control information element as the second control information element.
With the above construction, code tables (the first and second control information tables) for decoding the two coded control information elements can be specified by the respective pointers.
The above object can also be fulfilled by a digital broadcast receiving apparatus for decoding a compressed code stream included in a received digital broadcast wave to reproduce image data, including: a code extracting unit for extracting two consecutive codewords from the compressed code stream that is made up of a sequence of variable length codewords; and a parallel decoding unit for decoding the extracted two codewords in parallel.
With the above construction, the digital broadcast receiving apparatus extracts two codewords from a compressed code stream transmitted on a digital broadcast wave and decodes them in parallel. Accordingly, a greater number of variable length codewords can be decoded within a fixed time period.
The above object can also be fulfilled by a DVD (Digital Versatile Disk) reproducing apparatus for decoding a compressed code stream recorded on a DVD to reproduce image data, including: a code extracting unit for extracting two consecutive codewords from the compressed code stream that is made up of a sequence of variable length codewords; and a parallel decoding unit for decoding the extracted two codewords in parallel.
With the above construction, the DVD reproducing apparatus extracts two codewords from a compressed code stream recorded on a DVD and decodes them in parallel. Accordingly, a greater number of variable length codewords can be decoded within a fixed time period.